%% ---------------------------------------------------------------------
%% dyninsets.tex
%%
%% Created 2010-02-22 by Sohaib Ghani, Nathalie Henry-Riche, and
%% Niklas Elmqvist.
%% 
%% Intended for submission to IEEE InfoVis 2010.
%% ---------------------------------------------------------------------

%% ---------------------------------------------------------------------
%% Document class
%% ---------------------------------------------------------------------
\documentclass[journal]{vgtc}

%% ---------------------------------------------------------------------
%% Packages 
%% ---------------------------------------------------------------------

%% These three lines bring in essential packages: ``mathptmx'' for Type 1 
%% typefaces, ``graphicx'' for inclusion of EPS figures. and ``times''
%% for proper handling of the times font family.
%% We encourage the use of mathptmx for consistent usage of times font
%% throughout the proceedings. However, if you encounter conflicts
%% with other math-related packages, you may want to disable it.
\usepackage{mathptmx}
\usepackage{graphicx}
\usepackage{times}

% Multi-line comments
\usepackage{verbatim}

%% Package to allow for subfigures
\usepackage{subfigure}

%% Use this for zero \parindent and non-zero \parskip, intelligently.
\usepackage{parskip}

%% URLs
\usepackage{url}

%% Allow for this line if you want the electronic option to work properly
\vgtcinsertpkg

%%%% NAT's Shortcuts
\newcommand{\BG}{Bring \& Go}
\newcommand{\DI}{Dynamic Insets}
\newcommand{\tec}{{\it Techniques}}
\newcommand{\den}{{\it Densities}}
\newcommand{\task}{{\it Tasks}}
\usepackage{color}
\newcommand{\nat}[1]{ \textcolor{blue}{#1}}

%% ---------------------------------------------------------------------
%% Paper metainformation
%% ---------------------------------------------------------------------

%% If you are submitting a paper to a conference for review with a double
%% blind reviewing process, please replace the value ``0'' below with your
%% OnlineID. Otherwise, you may safely leave it at ``0''.
\onlineid{0}

%% declare the category of your paper, only shown in review mode
\vgtccategory{Research}

%% ---------------------------------------------------------------------
%% Title, author(s), and affiliations
%% ---------------------------------------------------------------------

% Paper title
\title{Dynamic Insets for Context-Aware Navigation\\ in Large-Scale
  Networks}

%% Authors
\author{Sohaib Ghani, Nathalie Henry, and Niklas Elmqvist,
  \textit{Member, IEEE}}

%% Author information
\authorfooter{
\item Sohaib Ghani is with Purdue University in West Lafayette, IN,
  USA, E-mail: sghani@purdue.edu.
\item Nathalie Henry is with Microsoft Research in Seattle, WA, USA,
  E-mail: nathalie.henry@microsoft.com.
\item Niklas Elmqvist is with Purdue University in West Lafayette, IN,
  USA, E-mail: elm@purdue.edu.}

%% Short author title
\shortauthortitle{Ghani \MakeLowercase{\textit{et al.}}: Dynamic Insets}

%% Manuscript note
\manuscriptnote{Submitted to IEEE InfoVis 2010.  Please do not
  redistribute.}

%% In preprint mode you may define your own headline.
\preprinttext{Submitted to IEEE InfoVis 2010.  Please do not
  redistribute.}

% Teaser figure goes here (encouraged for InfoVis 2010)
\teaser{
  \resizebox{0.97\textwidth}{!}{\includegraphics{figures/tease_map}}
  \caption{The Dynamic Insets technique for a map of Purdue University
    and environs showing insets for off-screen nodes with surrounding
    context.}
  \label{fig:dynamic-insets}
}

% ----------------------------------------------------------------------
% Abstract
% ----------------------------------------------------------------------
\abstract{Viewing and interacting with large networks such as maps,
  social networks, or airline routes is a central theme in
  visualization, and retaining both overview and detail during
  navigation in such networks is a difficult task.  
  Commonly used graph navigation techniques are pan, zoom, and
  bird's eye views.
  These techniques are often tedious and cumbersome, especially when
  objects of interest are placed far apart.  
  We present a navigation technique called Dynamic Insets that
  provides context awareness for large scale networks.  
  Dynamic Insets utilize the topological structure of the network to
  draw a dynamic inset for off-screen nodes that shows a portion of
  the surrounding area for the destinations of links leaving the edge
  of the screen.  
  We implement and discuss the use of Dynamic Insets for a number of
  examples like maps, social networks, and software diagrams.  
  We also present results from a user study that shows that our new
  technique is significantly more efficient than existing techniques
  for context-aware graph navigation.}

%% Keywords that describe your work.  Will show as 'Index Terms' in journal
%% please capitalize first letter and insert punctuation after last keyword
\keywords{Node-link diagrams, topology-aware navigation,
  focus+context, degree-of-interest, interaction, evaluation.}

%% Note: ACM CCS keywords not used in VGTC journal version.

%% ---------------------------------------------------------------------
%% Document Beginning
%% ---------------------------------------------------------------------
\begin{document}

%% The ``\maketitle'' command must be the first command after the
%% ``\begin{document}'' command.  It prepares and prints the title block.

%% ---------------------------------------------------------------------
%% INTRODUCTION
%% ---------------------------------------------------------------------
%% the only exception to this rule is the \firstsection command
\firstsection{Introduction}

\maketitle

Interacting with road networks in a handheld GPS or on map websites
like Google Maps or Bing Maps is just one example of large-scale
networks that millions of people use in their everyday life, and there
are many other examples in more specialized applications for social
network analysis, network topology design, and graph visualization.
Navigation in these networks is usually performed using a sequence of
pan and zoom operations~\cite{Furnas1995}, sometimes using a bird's
eye view.
For example, to move from one position in a large network to another
position far away, the common approach is to zoom out, pan to that
position, and finally zoom in~\cite{vanWijk2003}.  
However, this can be tedious, ineffective, and potentially
disorienting~\cite{Furnas1986, Furnas1995}.

A recent trend in graph navigation is to utilize the topological
structure of the network to enhance navigation; examples include
the link sliding and Bring \& Go techniques~\cite{Moscovich2009}.
However, these techniques do not provide an awareness of the context
around the destination nodes, context that can be useful when
deciding which node to travel to next.

In this paper, we present a navigation technique called
\textit{Dynamic Insets} that supports multi-focus interaction during
navigation in large scale networks.  
Drawing inspiration from the age-old discipline of cartography, we add
dynamically updated map insets that show a small part of the
surrounding area for the destinations of links leaving the boundary of
the screen (Figure~\ref{fig:dynamic-insets}).  
The inset can be clicked to automatically animate the user's viewpoint
to the desired destination.
We also introduce interest functions that control which off-screen
nodes should be made visible through insets.  
By choosing between different interest functions, the user could opt
to show all neighboring nodes, or filter to show only nearby gas
stations (for a map application), central actors (for a social
network), or access points (for network topology design).

Graph visualization is a core topic in information visualization
research~\cite{Shneiderman1996}, and effective navigation techniques
are essential for managing large graphs~\cite{Herman2000}.
To further motivate our work, we present a number of examples and
applications for the Dynamic Insets technique, including social
network visualization, software diagrams, and geographic maps.  
To validate our new technique, we also perform a controlled experiment
involving human subjects where we compare it to the Bring \& Go
technique of Moscovich et al.~\cite{Moscovich2009}.  
Our results show that our technique significantly helps users in
maintaining an awareness of both the details as well as the overview
of the network, thereby speeding up the navigation process in general.

This paper is structured as follows: We first survey the related work
in area.  
We then present the Dynamic Insets technique.  
We describe a controlled user study where we compare the technique to
Bring \& Go~\cite{Moscovich2009}.  
We present and discuss our results and give some practical examples. 
We close with a summary and our plans for future work.

%% ---------------------------------------------------------------------
%% RELATED WORK
%% ---------------------------------------------------------------------
\section{Related Work}

In their survey on graph visualization and navigation, Herman et
al.~\cite{Herman2000} emphasize navigation and interaction techniques
as essential components of large graph visualization. 
In this section, we review relevant work on common navigation
techniques, off-screen awareness and navigation, and techniques for
navigation in networks.

\subsection{Common Navigation Techniques}

\subparagraph{Scrolling}

Scrolling is a common technique to navigate in large spaces such as
documents.
Scrolling interfaces using widgets such as scrollbars
may become cumbersome when the space to explore is very large.  
Multiple improvements have been proposed to address this, such as
adjusting the level of zoom from the scrolling speed
(SDAZ)~\cite{Igarashi2000}, or taking advantage of the context to
optimize scrolling direction, speed, and zoom level~\cite{Ishak2006}. 
However, to inspect a large 2D workspace, scrolling still requires a
lot of effort from the user.

\subparagraph{Pan and Zoom}

Pan and zoom are commonly used navigation techniques in everyday
applications.
Since the original infinitely zoomable canvas proposed in
Pad~\cite{Perlin1993}, there has been a large amount of work in this
area. 
Furnas and Bederson~\cite{Furnas1995} designed a space-scale formalism
for describing and understanding pan and zoom interactions.
Multiple studies show that combining zooming and panning is more
efficient than panning~\cite{Bourgeois2002, Furnas1995,
  vanWijk2003}. 
However, pan and zoom may become tedious when exploring distant
objects in large spaces~\cite{Furnas1986}.  
More importantly, this technique may frustrate users when navigating
in graphs as the destination is often known (the other end of the
link) but these techniques do not take advantage of that information.

\subparagraph{Split Screens}

Splitting the viewport into several parts is another standard method
for interacting with large visual spaces, and allows the user to gain
awareness of multiple regions of the space (possibly far away from
each other). 
Shoemaker and Gutwin~\cite{Shoemaker2007} present a technique bridging
split-screens and scrolling.  
This technique automatically splits the viewport when a user is
reaches sufficiently far from the focus point. 
However, the main disadvantage of split-screen techniques is the loss
of intervening context details~\cite{Elmqvist2008}.

\subparagraph{Overview+Detail}

Overview and detail techniques~\cite{Plaisant1995}
use
multiple windows to present the overview of the whole workspace as
well as the current region in focus. 
The overview often includes a visual cue indicating the current
viewport.
This marker may be moved by the user to navigate to other region of
the space.
Hornbaek and Frokjaer~\cite{Hornbaek2001} showed that overview and
detail techniques are easy to use and can outperform panning and
fisheye views for some tasks. 
While these techniques have been shown to be effective in navigating
large networks~\cite{Hornbaek2002, Kaptelinin1995}, additional
interaction is required to manage the windows. 
Users have to perform a series of inspections in the overview to
locate possible regions of interest. 
As overviews often occupy small screen space, the large
scaling factor becomes a hindrance in finding specific landmarks or
follow given elements such as links. 
Thus, the technique may degrade the overall experience as users
randomly move the visual cue of the viewport to find the region of
interest.

\subparagraph{Space Distortion Techniques}

Space distortion technique have also been used to navigate in
large spaces.  
Techniques such as fisheye views~\cite{Furnas1986} magnify
the focus region while the surrounding context is shown in less
detail.  
Rubber sheet stretching~\cite{Sarkar1993} is another model of
distorting 2D space. 
In this model, the space is stretched at the focus
point for navigation and context awareness.  
Elmqvist et al.~\cite{Elmqvist2008} give a space-folding technique
called M\'{e}lange that combines different parts of the visual space
so that multiple focus points and as much as possible of their
surrounding context are visible on the screen.
Other work show that distortion techniques can be efficient for
navigating in large networks~\cite{Schaffer1996} or for large steering
tasks~\cite{Gutwin2003}. 
However, space distortion suffers from a number of issues: the
transition between focus and context needs to be carefully
designed~\cite{Pietriga2008}, fisheyes may cause problems for
targeting tasks~\cite{Gutwin2002}, and Hornbaek et
al.~\cite{Hornbaek2001} showed that performance may be lower
compared to overview+detail techniques.

\subsection{Navigation to Off-Screen Targets}

\subparagraph{Visual Cues} 

Some techniques have been specifically designed to provide
awareness of off-screen targets.
Halo~\cite{Baudisch2003}, and its descendants
Wedge~\cite{Gustafson2008} and EdgeRadar~\cite{Gustafson2007},
indicate off-screen targets by adding visual cues to the border of the
viewport.
Another variation of these techniques is CityLights~\cite{Zellweger2003},
which displays shadows on the viewport borders. 
While these techniques give users awareness of the location of
off-screen targets, they do not provide a mechanism to reach them.

\subparagraph{Proxies}

Proxy-based techniques provide local copies of off-screen targets to
ease their selection. 
Drag-and-pop~\cite{Baudisch2003b} and Vacuum~\cite{Bezerianos2005} are
good examples of such techniques. 
As these techniques are primarily designed for selection rather than
navigation, they do not provide the context of targets, forcing
users to visit each of them to see the context.

\subparagraph{Proxies+Context} 

One of the most revelant techniques to ours is probably
WinHop~\cite{Partridge2007}.
WinHop introduces a space-multiplexing inset window to let users
explore the distant region without actually leaving the current
location. 
However, WinHop does not take advantage of context information such as
the network topology, so the user first has to select the node of
interest to expand.
This may also affect its ability to scale to very large visual spaces.

\begin{figure*}[tbh]
  \centering
  \resizebox{\textwidth}{!}{\includegraphics{figures/dyninsets-idea}}
  \caption{Dynamic construction of insets for a simple graph
    consisting of 7 nodes and 8 edges.  A is the source node ($n_s$).}
  \label{fig:dyninsets-idea}
\end{figure*}

\subsection{Navigation in Networks}

\subparagraph{Distortion Lenses} 

A few distortion techniques have been specifically designed for
graphs. 
EdgeLens~\cite{Wong2003} interactively distorts links around the focus
point to remove potential clutter. 
A work more related to our technique is the Bring-Neighbor
Lens~\cite{Tominski2006}, a lens that temporarily modifies the graph
layout to show all neighbors of the node in focus. 
However, this distortion lens has not been designed for navigation:
users can gain awareness of the neighbors, but are still required to
use a navigation technique such as pan and zoom to reach them.

\subparagraph{DOI}

Furnas~\cite{Furnas1986} showed that the visibility of
graph features can be controlled by the user through a degree of
interest (DOI) function.  
Nodes are ranked according to their topological distance to the focus
node in the graph.  
The graph may then be distorted to show the most interesting
information to the user. 
This principle has been employed for hierarchies~\cite{Plaisant2002}
and in large networks~\cite{Gansner2005, vanHam2009}. 
However, these techniques deform the graph, compromising the user's
mental map.

\subparagraph{Topology-aware Navigation}

Moscovich et al.~\cite{Moscovich2009} presented two navigation
techniques taking advantages of the topology information of the
network to ease navigation.
Their first technique, Link Sliding, provides guided panning and
zooming when continuously dragging along a link. 
The second technique, Bring \& Go, gathers the neighbors of a node of
interest and enables the user to navigate to one of these at a time,
animating the view to its original position. 
These techniques have been compared to overview+detail and pan and
zoom techniques.
Bring \& Go outperformed both of these, while Link Sliding had mixed
results. 
Regardless, from all the techniques presented in this section, these
are most relevant to ours. 
We designed Dynamic Insets to overcome the principal drawback of Bring
\& Go: the lack of context for off-screen targets, requiring 
navigation to see the context.

%Indeed, users have to navigate to each of the neighbors brought to
%gain awareness of their context.

%% ---------------------------------------------------------------------
%% DYNAMIC INSETS
%% ---------------------------------------------------------------------
\section{Dynamic Insets}

Dynamic Insets is a topology-aware navigation technique for providing
context awareness while traversing large-scale networks.
It uses the connectivity of the graph to bring off-screen neighbors of
on-screen nodes---and their context---into the viewport as insets
(Figure~\ref{fig:dynamic-insets}).
In this way, multiple destinations for visual links leaving the edge
of the screen can be explored without actually leaving the current
location; this is more generally known as \textit{multi-focus
  interaction}~\cite{Elmqvist2008}.
The insets are created by cutting out a region of the visual space
surrounding the off-screen neighboring nodes and bringing these
regions into the main viewport as small, nested viewports.
Figure~\ref{fig:dyninsets-idea} shows the basic idea, where a simple
network with three off-screen nodes of interest are shown on
the screen using dynamically created insets.

While the above description captures the essence of the Dynamic
Interest technique, there are several additional details concerning
\textit{which} off-screen nodes to include, how insets are created,
how they are laid out, and how we can display distance information
using the technique. 
We discuss these topics in the following sections.

\subsection{Degree-of-Interest Function}

Instead of trying to visualize \textit{all} off-screen targets, like
existing off-screen navigation techniques~\cite{Partridge2007},
Dynamic Insets uses the connectivity of the graph itself to determine
\textit{which} off-screen targets to include.
This means that the technique can handle even very large graphs. 

To give additional expressive power to the technique, we use the
concept of a \textit{degree-of-interest (DOI)
  function}~\cite{Furnas1986} to rank all off-screen nodes
in terms of their interest for a particular task.
The simplest imaginable DOI function is a binary one that uses a
neighbor relation between the set of visible nodes $V$ and an
off-screen node $n$:
$$
DOI(n, V)  = 
\left\{
\begin{array}{lr}
1 & \exists v \in V : \mathrm{neighbor}(n, v)\\
0 &  \mathrm{otherwise}
\end{array}
\right.$$

In other words, this function will assign 1 to all neighbors of
currently visible nodes, and 0 to all others. 
An important special case for this situation is where the user has
selected a particular source node $n_s$ to use as a focus point
(instead of all currently visible nodes in the viewport).  
The above DOI function can be trivially adapted for this purpose by
simply passing $V = \{ n_s \}$.

Given any DOI function of the above format, we rank all off-screen
nodes according to their current DOI values.
A certain number of the highest ranked off-screen nodes will be
selected depending on the number of dynamic insets to create.
Ties may be arbitrarily broken, for example using distance, so that
nearby nodes are given precedence over more distant ones.  
However, a better approach is to devise a modified DOI function that
takes distance into account:
$$DOI_{dist}(n, V) \:=  DOI(n, V) / \mathrm{dist}(n)$$
where dist$(n)$ calculates the distance from $n$ to the edge of
the screen.

The default setting for our technique is to use the standard DOI
function defined above, but to allow the user to select a focused
source node $n_s$ by clicking on it.
Clicking outside any node on the visual space will clear the current
source node and return to the default setting.

In addition, more esoteric interest functions are also possible,
including interest functions composed of several simpler interest
functions, or making use of domain-specific information.
Here follows some examples of such DOI functions for particular
applications:

\begin{itemize}
\item For a GPS application, interests could be assigned for nearby gas
  stations, shopping malls, or hospitals, weighted by distance;
\item For airline route selection (like the Delta Air Lines Route
  Map\footnote{\url{http://delta.innosked.com/}}), potential
  destinations could be ranked according to their ticket price, travel
  duration, or number of stops; and
\item For social network analysis, the interest of off-screen
  neighbors could be based on how recent the connection is.
\end{itemize}

\subsection{Insets}

Given that we have derived \textit{which} off-screen nodes to make
visible on the screen, the next step is to actually create the insets.
Insets are small rectangular regions containing the target node and
its surrounding context in the visual space.
They have a visual border to differentiate them from the visual space
in the main viewport, and they are laid out on the edge of the screen
to coincide where the link they are associated with leaves the main
viewport (if possible, see the next section).

Figure~\ref{fig:dyninsets-idea}(c) shows the inset for three
off-screen nodes in a simple graph. 
Insets are not static, but the viewport in each inset area can be
interacted with, such as panning or zooming in and out (left-dragging
and using the mouse wheel in our implementation, respectively).
Most importantly, clicking an inset will automatically animate the
position of the user's viewport to the location of the target node in
the inset.
This both provides a quick way of navigating in the graph, and also
makes the path from source to destination clearly visible to the user,
thereby reinforcing their awareness of the entire visual space.

\subsection{Inset Layout}

We have designed a simple layout algorithm for positioning insets
along the edge of the screen. 
This algorithm has two main constraints:

\begin{itemize}
\item\textbf{Align insets with their links.} Insets should be placed
  so that their location on the edge of the screen coincides with the
  outgoing visual link that it is associated with.
  Ideally, the visual link on the main viewport and on the inset
  viewport should align perfectly to maximize the visual connection
  (all three insets in Figure~\ref{fig:dyninsets-idea}(c) exhibit this
  property).
\item\textbf{Avoid total occlusion.} For situations with a high
  density of outgoing links, insets may start to overlap.
  This is acceptable as long as no single inset is fully occluded by
  another inset.
\end{itemize}

For overlapped insets, the algorithm accordingly stacks the
insets as shown in Figure~\ref{fig:flipping}.  
We also implement a flipping interaction technique similar to that in
the M{\'e}lange technique~\cite{Elmqvist2008}, where the
user can hover the mouse cursor over an inset to bring it to the top.

\begin{figure}[htb]
  \centering
  \resizebox{\columnwidth}{!}{\includegraphics{figures/flipping}}
  \caption{Insets that overlap in space are stacked so that all insets
    in a stack are at least partly visible.  This allows them to be
    flipped through by hovering the mouse cursor over the visible
    part, bringing it to the top.}
  \label{fig:flipping}
\end{figure}

\subsection{Distance Awareness}
\label{sec:distance}

Our new technique does not naturally support distance awareness in its
visual representation like, for instance, Bring \&
Go~\cite{Moscovich2009}.
Nevertheless, we can easily extend the representation of individual
insets to incorporate this information.
Here are a few different alternatives:

\begin{itemize}

\item\textbf{Number:} The simplest approach is to add a number for the
  distance from the edge of the screen to the destination node shown
  in the inset (Figure~\ref{fig:distvis}(a)).  
  Our implementation uses this method.

\item\textbf{Border Color:} A quantitative color scale (i.e.,
  a heatmap) can be used for the inset border to 
  convey distance (Figure~\ref{fig:distvis}(b)). 

\item\textbf{Transparency:} Modulating the transparency of the inset:
  distant nodes nearly translucent, nearby ones opaque
  (Figure~\ref{fig:distvis}(c)).

\item\textbf{Size:} Scaling the size of the inset so that distant
  destinations are smaller than nearby ones
  (Figure~\ref{fig:distvis}(d)).

\item\textbf{Overview map:} Distance information could also be shown
  on an overview map where both the extents of the main viewport as
  well as the position of each inset is shown from above.
\end{itemize}

\begin{figure}[htb]
  \centering
  \resizebox{\columnwidth}{!}{\includegraphics{figures/distvis}}
  \caption{Four different alternatives for distance visualization: (a)
    actual number, (b) border color scale, (c) inset transparency, and
    (d) inset size.}
  \label{fig:distvis}
\end{figure}

\subsection{Implementation Notes}

We have implemented Dynamic Insets in a graph visualization built
using Java and the Piccolo toolkit~\cite{Bederson2004}. 
Our algorithm first calculates DOI values for all off-screen nodes and
ranks them using a priority queue. 
Given a specific budget $N$ of the maximum number of insets to
display, the $N$ most highly-ranked off-screen nodes are selected and
cameras are placed at their locations.
A layout algorithm tries to optimize the location of the insets
associated with each camera on the screen border.
This algorithm will first strive to preserve link alignment, but,
failing that, will stack overlapping insets to ensure that no inset is
fully occluded.
If there are two insets for the same node but for different links, the
layout algorithm will combine these insets if they are located within a
specific distance of each other on the canvas.
  
%% ---------------------------------------------------------------------
%% USER STUDY
%% ---------------------------------------------------------------------
\section{Controlled Experiment}

We conducted a user study to validate that the Dynamic Insets
technique does provide efficient and context-aware graph navigation.
Here we describe our methods, present the results, and discuss them.

%-------------------------------------------------------------------------
\subsection{Method}

\subsubsection{Participants and Apparatus}

We recruited 12 participants balanced for age and gender, and screened
to not be color-blind.  
We required our participants to be computer scientists so that would
all have at least basic knowledge of graphs.  
The participant pool consisted of 6 males and 6 females, with ages
ranging from 22 to 47.  
Each participant used a 3.00 GHz dual-core PC with 4 GB of memory,
running Microsoft Windows Vista, and equipped with a 21'' flat-screen
monitor set to a resolution of 1600$\times$1200.  
The size of the visualization was 1000$\times$1000 pixels.

\subsubsection{Techniques}

We used our \DI\ (DI) technique as described in this paper.  Moscovich
et al.~\cite{Moscovich2009} showed that navigation techniques taking
advantage of graph topology outperforms traditional techniques such as
pan and zoom, and bird's eye views.  In particular, the \BG\ (BG)
technique presented in that paper outperformed all other techniques.
Thus, we decided to compare our technique to \BG.

We reimplemented \BG, tuning the animation speed to 500ms for bringing
the neighbors and 600ms for the animation when traveling to the
destination.
We decided to suppress BG's zooming-out effect for the animated travel
to make the two techniques equivalent.

\subsubsection{Tasks}

We used the first task proposed by Moscovich et
al.~\cite{Moscovich2009} since it captures awareness of direct
neighbors.  We also included two additional tasks to capture context
awareness for each individual neighbor.

\begin{description}
 \item[CN]\textbf{CountNeighbors.}  How many neighbors of the node
   named ``cat'' are vegetables?
 \item[CC]\textbf{CloseContext.} Which neighbor of the ``cat'' node is
   located in the center of a \textbf{red} circle?  (The diameter of
   the circle is small enough to be fully visible in the insets
   provided by \DI.)
 \item[DC]\textbf{DistantContext.} Which neighbor of the ``cat'' node
   is in the center of a \textbf{red} circle? (The diameter of the
   circle is larger than the size of the insets provided by \DI.)
\end{description}

The reason for including two different context tasks was to force
participants to have to zoom and pan the insets in the DI condition.
We were interested in investigating whether this required interaction
would cause the technique to exhibit worse performance than BG.

\subsubsection{Datasets}

To measure the performance of the techniques in realistic conditions,
we selected two datasets with two \den: sparse vs.\ dense.  However,
to allow us to strictly control the network topology, we did not
generate complete graphs, but only a subset of those nodes and edges
involved in a particular task.  This also allows us to keep the
experiment to a reasonable length and limit the user's fatigue and
frustration (potentially induced by visiting a very large number of
neighbors).

To achieve this, our graphs had a star structure with the source node,
labeled ``cat'', at the center of the star.  We then created 20
potential destination nodes as neighbors to ``cat'' (level 1), each in
turn having an additional four local neighbors (level 2).  Thus, we
had a total of 101 nodes and 100 edges.  All level 1 neighbors were
located at random distances from the source node, but sufficiently
distant to be outside of the viewport when viewing the source ``cat''
node at default magnification level (pan and zoom was disabled).
Level 2 neighbors were arranged equidistantly in a circle around their
level 1 parent---the size of this circle was small enough to fit
inside the insets for the CC task, whereas it was larger than the
insets for the DC task.

To achieve different graph densities, we varied not the graph size but
the concentration of the destination nodes (level 1) in space:

\begin{itemize}
\item\textbf{Sparse.} The level 1 neighbors are equally distributed in
  a circle around the source node (Figure~\ref{fig:socnet-sparse}).
\item\textbf{Dense.} The level 1 neighbors are all placed in a
  $90^{\circ}$ arc within $45^{\circ}$ of the horizontal to the right
  of the source node (Figure~\ref{fig:socnet-dense}).
\end{itemize}

This strategy lets us keep the number of neighbors to visit stable
while reproducing the artefacts induced by both sparse and dense
graphs.
More specifically, for the dense case, it causes high overlap for
insets that mimics a large graph without penalizing the BG technique.
For the DI technique, however, users will be forced to flip between
insets to find the correct target.
Again, we wanted to investigative whether this extra interaction would
impact the performance of the DI technique.

\subsubsection{Experimental Design}

Given the above factors, we used a within-subject
full-factorial design: 2 navigation techniques ($N$) $\times$ 2
densities ($D$) $\times$ 3 tasks ($T$) $\times$ 3 repetitions = 24
unique conditions.
We counterbalanced the order of the techniques.  
The order of the tasks was fixed and graphs were randomly generated
for each trial, including the number of targets (for CN), and the
position of the red circle (for CC and DC).  
With 12 participants, we collected time and correctness for a total of
432 individual trials.

\subsubsection{Procedure}

Participants received training before each technique and each task.
We ensured they answered correctly before perfoming the timed tasks.
For each trial, participants clicked on a button to indicate that they
had finished reading the description of the task and were ready to
begin, and pressed the space bar when they were done.  
The application recorded accuracy and completion time.  
The completion timer started only after each navigation technique had
been first activated (i.e., after the initial BG animation had ended).
We did not enforce any time limit.  
After the experiment, we collected user preferences and comments using
a questionnaire.  
The study lasted approximately one hour, including the initial
training session and the post-experimental questionnaire.

\subsubsection{Hypotheses}

\begin{description}
\item[H1] For CountNeighbors, DI will perform as well as BG for both
  correctness and completion time.
\item[H2] For CloseContext, DI will be faster than BG because
  there is no need to travel to a neighbor in DI to see its context.
\item[H3] For DistantContext, DI will be faster than BG in the sparse
  graph because panning and zooming in each inset for DI is easy.
  However, for dense graphs, BG will be faster because the insets in
  DI overlap with each other, requiring additional interaction.
\end{description}

\subsection{Results}

We averaged measurements for all repetitions for each condition.
Below we first discuss the correctness and then the timing results.

\subsubsection{Correctness}

Correctness was high: 97 \% across all tasks.
Table~\ref{tab:correctness-effects} summarizes the main effects on
correctness for all factors, analyzed using logistic regression.  
As the table shows, only Task $T$ had a significant effect.  
We studied this using a Tukey HSD, and found that the only significant
difference was that the CountNeighbor task was less accurate than the
CloseContext task ($t = 2.05, p = .04$).  
For the CountNeighbor task, the mean correctness was 93 \% for both
navigation types with no significant difference between them ($F(1,
11) = .08, p = 0.78$).

\begin{table}[htb]
  \centering
  \begin{tabular}{|c|c|r|r|r|}
    \hline
    \textbf{Task} & 
    \textbf{Factors} & 
    \textbf{df, den} &
    \textbf{F} &
    \textbf{p}\\
    \hline\hline
    All & Navigation type (N) & 1, 11 & 0.08 &\\
    & Density (D) & 1, 11 & 0.08 & \\
    & Task (T) & 2, 22 & 3.36 & *\\
    \hline
  \end{tabular}\\
  ~* = $p \le 0.05$, ** = $p \le 0.001$.
  \caption{Effects of factors on correctness (logistic regression).}
  \label{tab:correctness-effects}
\end{table}

\subsubsection{Completion Time}

Table~\ref{tab:time-effects} summarizes the significant effects on
completion time using a repeated-measures analysis of variance
(RM-ANOVA).  
We found that the completion time violated the normality assumption of
the ANOVA, so we analyzed the logarithm of the times.
Other assumptions were met.  
Figure~\ref{fig:time} shows boxplots for the completion time as a
function of the navigation type $N$ and other factors.  
In particular, we analyzed the task factor $T$ using a Tukey HSD and
found that all pairwise differences were significant ($p < .001$) in
the order DC $>$ CN $>$ CC (completion time decreasing, with CC being
fastest).

\begin{table}[htb]
  \centering
  \begin{tabular}{|c|c|r|r|r|}
    \hline
    \textbf{Task} & 
    \textbf{Factors} & 
    \textbf{df, den} &
    \textbf{F} &
    \textbf{p}\\
    \hline\hline
    All & Navigation type (N) & 1, 11 & 205.37 & **\\
    & Density (D) & 1, 11 & 2.31 & \\
    & Task (T) & 2, 22 & 85.97 & **\\
    & V * T & 2, 22 & 229.75 & **\\
    & D * T & 2, 22 & 9.82 & **\\
    & V * D * T & 2, 22 & 3.46 & *\\
    \hline
    CN & Navigation type (N) & 1, 11 & 6.26 & **\\
    & Density (D) & 1, 11 & 1.92 & \\
    \hline
    CC & Navigation type (N) & 1, 11 & 559.58 & **\\
    & Density (D) & 1, 11 & 7.59 & *\\
    \hline
    DC & Navigation type (N) & 1, 11 & 34.93 & **\\
    & Density (D) & 1, 11 & 3.89 & \\
    \hline
  \end{tabular}\\
  ~* = $p \le 0.05$, ** = $p \le 0.001$.
  \caption{Effects of factors on time (RM-ANOVA).}
  \label{tab:time-effects}
\end{table}

\begin{figure*}[tbh]
  \centering
  \subfigure[All tasks combined.]{%
    \resizebox{0.32\textwidth}{!}{\includegraphics{plots/time-vis}}
    \label{fig:time-vis}
  }
  \subfigure[Task $T$.]{%
    \resizebox{0.32\textwidth}{!}{\includegraphics{plots/time-visxtask}}
    \label{fig:time-visxtask}
  }  
  \subfigure[Density $D$.]{%
    \resizebox{0.32\textwidth}{!}{\includegraphics{plots/time-visxdensity}}
    \label{fig:time-visxdensity}
  }
  \caption{Completion time as function of navigation type $N$ and
    the other experimental factors.}
  \label{fig:time}
\end{figure*}

\subsection{Discussion}

We can summarize our findings as follows (discussed below):
\begin{itemize}
\item Bring \& Go is faster than Dynamic Insets for CountNeighbors,
  but with no difference in accuracy (partially confirming H1);
\item Dynamic Insets are significantly faster than Bring \& Go for the
  CloseContext task (confirming H2); and
\item Dynamic Insets are faster than Bring \& Go for the
  DistantContext task (partially confirming H3).
\end{itemize}

\subsubsection{Explaining the Results}

The results from our study obey our intuition, but there are some
surprises as well. 
Collectively, as we correctly hypothesized, Dynamic Insets are faster
than the Bring \& Go technique (Figure~\ref{fig:time-vis}). 
This is clearly an effect of the user being able to see the off-screen
nodes along with their context without the need to travel to each node.

However, the fact that Dynamic Insets were significantly slower than
Bring \& Go for the CountNeighbor task is a bit of a surprise
(Figure~\ref{fig:time-visxtask}); we had expected the techniques to be
comparable in time.
We think the reason for this effect is that users had more screen
space to cover for DI than for BG: for Bring \& Go, all neighbors are
grouped together close to the center node, whereas for Dynamic Insets,
the neighbors are spread out in insets placed around the edge of the
screen.
 
As hypothesized, Dynamic Insets are significantly faster than Bring \&
Go for the CC task (Figure~\ref{fig:time-visxtask}).  
According to the same figure, they are also faster for the DC task,
which went against our hypothesis.
It seems that the benefit of being able to see the context surrounding
a node without having to travel there clearly outweights the extra
interaction needed to flip between stacked insets in the dense case.
In fact, density had no overall significant main effect on completion
time (Figure~\ref{fig:time-visxdensity}). 
This is surprising, but shows that both Bring \& Go and Dynamic Insets
are robust against locally high node densities.

The post-questionnaire results also showed that all participants
preferred DI to BG. 
Most of them explained that BG required them to travel to the
neighbors' locations to assess the context, whereas the context was
easily accessible on the viewport using DI.  
Several participants stated that even with insets overlapping and the
need to use the zoom inside the inset, DI was still far less tedious
than BG.

\subsubsection{Limitations and Generalizations} % of the Results}

As it is often the case with controlled experiments, we had to make a
large number of decisions on how to design our study. 
For example, to keep our experiment at a reasonable length, we chose
not to include standard techniques such as pan and zoom, and bird's eye
views.  
We based this decision on Moscovich et al.'s~\cite{Moscovich2009}
study that demonstrated that the Bring \& Go technique outperformed
these. 
From our study results, we can conclude that Dynamic Insets outperform
Bring \& Go for all context-related tasks. 
Therefore, we can reasonably argue that \DI\ outperforms standard
techniques such as pan and zoom, or bird's eye views for these tasks.  

However, further experiments are required to study how all these
techniques help users maintain a mental map of the network and
preserve distance awareness. 
For example, Bring \& Go distorts the network (potentially breaking
the users' mental map) but uses the layout of the neighbors brought to
maintain some distance awareness. 
\DI\ does not distort the network but introduce additional visual
encodings for indicating the distance (discussed in
Section~\ref{sec:distance}). 
It is difficult to evaluate the impact of
these compromises.  
For this particular point, standard techniques such as pan and zoom
may perform better.

Finally, despite our claim for Dynamic Insets to scale to large
graphs, we performed our controlled experiment using a small network
consisting of only 101 nodes and 100 edges.
We argue that \DI\ and \BG\ only act on local sub-graphs and thus that
the results found in our experiment are generalizable to larger
networks, particularly for small-world networks~\cite{Watts1998} (like
social networks) that are locally dense but globally sparse.
However, it would still be interesting to confirm this hypothesis.

%% ---------------------------------------------------------------------
%% EXAMPLES
%% ---------------------------------------------------------------------
\section{Examples}
\begin{figure}[htb]
  \centering \subfigure[Social network used in the experiment (Sparse 
    case with CloseContext).]{
    \resizebox{\columnwidth}{!}{\includegraphics{figures/socnet-sparse}}
    \label{fig:socnet-sparse}
  }
  \subfigure[Social network used in the experiment (Dense
    case with CloseContext).]{
    \resizebox{\columnwidth}{!}{\includegraphics{figures/socnet-dense}}
    \label{fig:socnet-dense}
  }
  \label{fig:socnet}
  \caption{Social network with the Dynamic Insets technique.}
\end{figure}

\subsection{Social Networks}

Social networks are the canonical application of graph visualization.
Using our Java framework, we implemented a simple social network
visualization and utilized our Dynamic Insets technique to showcase how
navigation can be improved in such networks.
Figure~\ref{fig:socnet-sparse} shows an example of this visualization
tool for the Sparse condition of the randomized dataset that we
utilized for the user study.
In this example, the destination nodes are arranged in a radial layout
at difference distances (all outside of the viewport) from
the center node.
Because there is no overlap between any insets, all links can be
aligned with their associated insets.

Figure ~\ref{fig:socnet-dense} shows our tool with a Dense example
from the controlled experiment.
All 20 destination nodes are in a $90^{\circ}$ arc to the right of the
source node, accordingly causing overlap between the insets.
The layout is unable to align all insets, but still ensures that
insets are stacked so that individual inset can always be accessed
using flipping.

\subsection{Maps}

The inspiration for the Dynamic Insets technique comes from
cartography, and, not surprisingly, there is excellent potential
for using the technique for cartographic applications.
To begin realizing this potential, we have implemented a map
scenario that uses static (i.e., not live) data from Google Maps.
Figure~\ref{fig:dynamic-insets} shows a map of Purdue University as
well as the twin cities of West Lafayette and Lafayette, IN.
We have modeled a connectivity graph (invisible) for a few locations
outside of the viewport; insets are automatically created for these
and laid out on the edge of the screen.   
This example clearly shows the benefit of contextual information from
the geographical features in the insets.

Note that because we are currently only modeling connectivity, and not
the geographical positions of the roads, some of the
insets are not correctly placed on the viewport border.
For example, the Chicago inset should really be aligned with
Interstate 65 leaving the viewport, but is instead aligned with a
straight line from the viewport to the city.
This is a limitation of our example and not the technique itself.

Our map application is similar to existing work in cartography; for
example, Karnick et al.~\cite{Karnick2009} present a method for
visualizing route maps with multiple focus points by showing overview
and detail views of the route within a single visual frame.  
However, their goal is to provide a printable version of a route map
rather than to facilitate navigation.

\begin{figure*}[htb]
  \centering
  \resizebox{0.63\textwidth}{!}{\includegraphics{figures/UML}}
  \caption{UML class diagram with dynamic insets for neighboring
    classes that are currently outside of the viewport. 
    The user can zoom and pan the insets, and clicking inside an inset
    will animate the viewport to the corresponding destination.}
  \label{fig:uml}
\end{figure*}

\subsection{UML Software Diagrams}

The Unified Modeling Language (UML) is a general-purpose modeling
language for software engineering.
UML diagrams come in different types for capturing both the dynamic
behavior and static structure of a system; examples include class,
component, activity, use-case, and deployment diagrams.

Regardless of type, UML diagrams for complex systems easily become
large and complex themselves.
Figure~\ref{fig:uml} shows an example of using Dynamic Insets for a
simple class diagram viewer where the relations between classes are
modeled using a graph (again not shown). 
As can be seen from the figure, the technique efficiently shows the
surrounding context of a class, even when the user has zoomed in to
study specific details of the diagram.

%% ---------------------------------------------------------------------
%% CONCLUSION
%% ---------------------------------------------------------------------
\section{Conclusion and Future Work}

We have presented a context-aware graph navigation technique that
utilizes the topology of a graph to dynamically create small inset
viewports for off-screen neighbors of visible nodes.
We give three examples showcasing the utility of the technique for
social networks, geographical maps, and software diagrams.
We also present results from a controlled experiment that shows that
our technique outperforms current state-of-the-art navigation
techniques for large-scale networks.

In our future endeavors we would like to design and evaluate
additional degree-of-interest functions.
Furthermore, we want to study the performance of different distance
mechanisms. 
We also plan to embed the technique in a real-world tool like Google
Maps or Bing Maps.

%% Acknowledgements (omitted in review mode)
%\acknowledgements{We would like to thank the anonymous participants
%  that participated in our experiment.}

% ----------------------------------------------------------------------
% Bibliography
% ----------------------------------------------------------------------
\bibliographystyle{abbrv}
\bibliography{dyninsets}

\end{document}
